// 题目要求：
// 给一个 n * m 的数组，表示地图，1 表示起点，2 表示客户位置，0 表示能通过的路，-1 表示不能达到的位置
// 问达到客户处的最短路径的方案数有几种？

// 解题思路：
// bfs 最短路径问题
// 定义 dist 数组，用于存放起点能到到的位置的最短路径的长度
// 定义 count 数组，用于存放从起点达到该位置的最短路径的方案数
// dist 初始化为 -1，表示没到达过这个位置
// count 初始化为 0，表示没有方案
// dist 起点初始化 0，表示从起点到起点的距离为 0
// count 起点初始化为 1，表示从起点到起点的方案为 1 种
// 进行层序遍历：
// 如果第一次达到某个位置，就更新 dist 数组
// 如果不是第一次达到，就判断到达这个位置的距离是不是最短距离，如果是就更新方案数


import java.util.*;



public class MeetCustomer {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int row;
    int col;
    int[] start = new int[2];
    int[] end = new int[2];
    int[][] dist;
    int[][] count;

    public int countPath (int[][] CityMap, int n, int m) {
        row = n;
        col = m;

        dist = new int[n][m];
        count = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dist[i][j] = -1;
                count[i][j] = 0;
                if (CityMap[i][j] == 1) {
                    start[0] = i;
                    start[1] = j;
                } else if (CityMap[i][j] == 2) {
                    end[0] = i;
                    end[1] = j;
                }
            }
        }

        dist[start[0]][start[1]] = 0;
        count[start[0]][start[1]] = 1;

        return bfs(CityMap);
    }

    public int bfs(int[][] CityMap) {
        Queue<int[]> queue = new LinkedList<>();

        queue.offer(start);

        while (!queue.isEmpty()) {

            int[] point = queue.poll();

            int a = point[0];
            int b = point[1];

            for (int i = 0; i < 4; i++) {
                int x = a + dx[i];
                int y = b + dy[i];

                if (x >= 0 && x < row && y >= 0 && y < col && CityMap[x][y] != -1) {
                    if(dist[x][y] == -1){
                        dist[x][y] = dist[a][b] + 1;
                        count[x][y] = count[a][b];
                        queue.offer(new int[] {x, y});
                    }else{
                        if(dist[a][b] + 1 == dist[x][y]){
                            count[x][y] += count[a][b];
                        }
                    }
                }
            }
        }

        return count[end[0]][end[1]];
    }
}
